arr = [-74,48,-20,2,10,-84,-5,-9,11,-24,-91,2,-71,64,63,80,28,-30,-58,-11,-44,-87,-22,54,-74,-10,-55,-28,-46,29,10,50,-72,34,26,25,8,51,13,30,35,-8,50,65,-6,16,-2,21,-78,35,-13,14,23,-3,26,-90,86,25,-56,91,-13,92,-25,37,57,-20,-69,98,95,45,47,29,86,-28,73,-44,-46,65,-84,-96,-24,-12,72,-68,93,57,92,52,-45,-2,85,-63,56,55,12,-85,77,-39]
# arr = [54, 26, 93, 17, 77, 31, 44, 55, 20]
import random
def Partition(l, low, height):
    pivot = random.randint(low, height)
    l[pivot], l[low] = l[low], l[pivot]
    pivotkey = l[low]
    while low < height:
        while low < height and l[height] >= pivotkey:
            height -= 1
        l[low] = l[height]

        # low += 1
        while low < height and l[low] < pivotkey: 
            low += 1
        l[height] = l[low]
        # height -= 1  # 按照正常的思路，应该执行这两个 low += 1， height -= 1 但是关键就错在，这两个值，会使low height指针重合后，再次发生偏移。 因为他们一定执行，不受限制。 所以不能加这两个语句，让他们在while 内部判断即可
    l[low] = pivotkey

    return low

def Qsort(l, low, height):
    if low < height:
        p = Partition(l, low, height)
        Qsort(l, 0, p-1)
        Qsort(l, p+1, height)


def QuckSort(l):                                               
    Qsort(l, 0, len(l) - 1)

QuckSort(arr)
print(arr)
